Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Valid Palindrome

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: sentence = "A man, a plan, a canal, Panama!"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: sentence = "Was it a car or a cat I saw?"
Output: true
Explanation: Explanation: "wasitacaroracatisaw" is a palindrome.

Example 3:

Input: sentence = "race a car"
Output: false
Explanation: Explanation: "raceacar" is not a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 105
  • s consists only of printable ASCII characters.

Solution

This problem aims to check if a given string is a palindrome. A palindrome is a word, phrase, number, or other sequences of characters that read the same forward and backward, ignoring spaces, punctuation, and capitalization. Our algorithm can leverage the two-pointer technique where one pointer starts at the beginning of the string, and the other one starts at the end. The two pointers move towards each other, checking if the characters they point to are the same.

Walkthrough of the algorithm

Let's take a detailed walkthrough of the code:

  1. The isPalindrome function starts by setting two pointers: 'i' at the start of the string and 'j' at the end.

  2. Then it enters a while loop which continues until the two pointers cross each other. Inside this loop:

    • The first inner while loop moves 'i' forward, skipping any characters that are not letters or digits, until it points to a valid character or it crosses 'j'.

    • The second inner while loop moves 'j' backward, skipping any characters that are not letters or digits, until it points to a valid character or it crosses 'i'.

  3. After finding valid characters at 'i' and 'j', it converts these characters to lowercase and checks if they're the same.

    • If they're not the same, the function immediately returns false since the string can't be a palindrome if these characters are different.

    • If they are the same, 'i' is incremented and 'j' is decremented, and the loop continues to the next pair of characters.

  4. If the while loop completes without finding any unequal pairs of characters, the function returns true, indicating that the string is a palindrome.

Image

Code

Here is the code for this algorithm:

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Two-pointer traversal: The algorithm uses two pointers, i starting from the left and j from the right, and moves them inward toward each other. The loop runs until the two pointers meet or cross over, meaning we traverse the string once. This results in a time complexity of , where N is the length of the input string.

  • Nested loops (for skipping non-alphanumeric characters):

    • Within the main loop, we use two while loops to skip non-alphanumeric characters. Each of these inner loops also runs at most N times in total, as each character is only skipped once. Even though the loops are nested, their total number of iterations is still proportional to the size of the string.
  • Character comparisons: Each valid alphanumeric character is compared after converting to lowercase, which is a constant time operation, .

Overall time complexity: .

Space Complexity

  • Constant space: The algorithm only uses a few extra variables (i, j) and performs character operations in place. No additional data structures are used that scale with the input size.

Overall space complexity: .

Valid Palindrome (easy)
Rotate List (medium)
Mark as Completed

On this page

Problem Statement

Solution

Walkthrough of the algorithm

Code

Complexity Analysis

Time Complexity

Space Complexity